/*
 *
 *
 *
 * [42] 连续子数组的最大数之和,
 * 例如输入的数组为{1, -2, 3, 10, -4, 7, 2, -5}，和最大的子数组为｛3, 10, -4, 7,
 * 2}。因此输出为该子数组的和18
 *
 * g++ test_cpp.cpp -ggdb -std=c++11
 */

// @lc code=start

#include <float.h>

#include <algorithm>
#include <iostream>
#include <vector>
#define INT_MAX 2147483647
#define INT_MIN (-INT_MAX - 1)
using namespace std;

class Solution
{
 public:
  // /**
  //  * @brief 题目42 输入一个整型数组，数组里有正数也有负数。数组中一个或连
  //  * 续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)
  //  *
  //  * @param arr 输入数组
  //  * @return 最大的连续子数组和
  //  */
  // int findGreatestSumOfSubArray(vector<int> arr)
  // {
  //   if (arr.size() < 0)
  //   {
  //     cout << "Array must contain an element" << endl;
  //     return -1;
  //   }
  //   // 记录最大的子数组和，开始时是最小的整数
  //   int max = INT_MIN;
  //   // 当前的和
  //   int curMax = 0;
  //   // 数组遍历
  //   for (int i : arr)
  //   {
  //     // 如果当前和小于等于0，就重新设置当前和
  //     // 如果遍历到第i-1th数，准备往i遍历时，curMax表示截止到i-1时最大子序列和的情况
  //     if (curMax <= 0)
  //     {
  //       curMax = i;
  //     }
  //     // 如果i-1和大于0，累加i作为i的当前和
  //     else
  //     {
  //       curMax += i;
  //     }

  //     // 更新记录到的截止到i的最大的子数组和
  //     if (max < curMax)
  //     {
  //       max = curMax;
  //     }
  //   }

  //   return max;
  // }

  /* 使用动态规划，选与不选的问题
  /* F（i）：以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变
  /* F（i）=max（F（i-1）+array[i] ， array[i]）
  /* res：所有子数组的和的最大值
  /* res=max（res，F（i））
  */
  int FindGreatestSumOfArray(vector<int> array)
  {
    int res = array[0];
    for (int i = 1; i < array.size(); i++)
    {
      // array[i]对应dp[i]，覆盖array[i]节省空间复杂度
      array[i] += std::max(nums[i - 1], 0);
      res = std::max(res, array[i]);
    }
    return res;
  }
};

int main()
{
  class Solution solute;
  vector<int> arra1 = {1, -1, 5, -8, 9, 10, 20};
  vector<int> arra2 = {-1, -10, 5, 1, 1, 0, -30};
  int sum1 = solute.findGreatestSumOfSubArray(arra1);
  int sum2 = solute.findGreatestSumOfSubArray(arra2);

  cout << "sum1: " << sum1 << endl;
  cout << "sum2: " << sum2 << endl;

  return 0;
}

// @lc code=end
